1. Field of the Invention
This invention relates to the stabilization of asynchronous state machines, especially those in which the operation passes from state to state as the result of being actuated by a series of signals that are not synchronous with each other and may occur so nearly simultaneously as to cause the machine to follow an improper sequence of progression.
2. The Prior Art
Some computing systems operate on the basis of having information transmitted by signals that are synchronized with each other, and specific amounts of time are allocated to the performance of each operating step or task. However, some steps or tasks can be completed much more rapidly than others, but in synchronous systems, the time required to perform the slowest step or task is the minimum time that must be allocated for all others synchronous with the slowest.
By allowing various parts of the system to complete their steps or tasks as quickly as possible and allowing them to operate asynchronously with respect to other parts, even closely related ones, the overall speed of operation can be increased.
The present invention was conceived in response to the need to speed up operation of a certain synchronous system, and the new concept successfully allows asynchronous operation that is about three times as fast as it would be if the operation had to be controlled on a synchronous basis.
One of the principal dangers in asynchronous operation is that two or more signals that should arrive at a given point in the system at different times will occasionally arrive so nearly simultaneously as to constitute a misleading result. Digital signals have two different values, commonly referred to as a 1 and a 0, and digital circuits normally respond to each value of an input signal in a specific way. Although digital signals are frequently described as if the time for such signals to shift from one of the values to the other were instantaneous, that is not an accurate description. A finite, though small, time is required for the signal to stabilize in its new value, and if another signal arrives with an overlapping transition time, the circuit that is supposed to respond in a certain way to one of the signals may not do so. The condition of having two signals contend with each other for control of a digital system or part of such a system on the basis of which signal arrives first is known as a race condition.